1. Field of the Invention
The present invention relates to an approximate calculator for a non-linear function, an approximate calculator for a function log (1+e−x) an approximate calculator for a function log (ea+eb) and a MAP decoder using the same.
2. Related Art
A turbo decoder for decoding a turbo code is proposed. The turbo code includes parallel concatenated convolutional codes with interleaving. The turbo decoder receives and decodes the turbo code while correcting errors. Referring to FIG. 7, the turbo decoder includes two soft-output decoders 101, 102, two interleavers 103, 104, a deinterleaver 105, and a hard decision block 106. The soft-output decoders 101, 102 perform decoding utilizing MAP (Maximum A Posteriori) algorithm as follows.
Referring to FIG. 8, a probability pdf that a bit is “0” and a probability pdf that a bit “1” are calculated for all bits of the received data X(t) using a probability density function of the received data at step 201. Next, probabilities (state transition probabilities) γ are calculated for all branches of a trellis at step 202. At step 203, probabilities α (state probabilities) are calculated by forward iterations for all states and for all trellis levels (i.e., all bits of the received data). At step 204, the probabilities (state probabilities) β are calculated by backward iterations for all states and for all trellis levels.
Next, Information symbol likelihood λ is calculated for all trellis levels using the probabilities α, β. A priori likelihood (LDK) is calculated for all trellis levels based on information symbol likelihood λ at step 206, and it is converted to a priori probabilities corresponding to the respective states and fed back to step 202. At step 207, hard decision is made based on information symbol likelihood λ so that the received data is decoded.
This MAP decoding process may be implemented by a calculator shown in FIG. 9. That is, the probabilities pdf, the probabilities α, β, γ the information symbol likelihood λ, the a priori likelihood LDK and a priori probabilities prb can be computed by using the respective formulas shown in FIG. 9. However, it is impractical to implement the calculator by hardware or software, because the number of bits required for representing intermediate results is large.
Then it is proposed that one of various algorithms is employed so that the MAP decoding calculator is implemented by a smaller circuit. For example, Log-BCJR algorithm (S. Bebedetto et. al, “Soft-output decoding of parallel concatenated convolutional codes”, ICC 96) is known as an algorithm that enables alleviation of computational complexity so that the precision of decoding is maintained. According to Log-BCJR algorithm, the operations corresponding to the respective blocks shown in FIG. 9 are executed with respect to exponent parts, that is, the operations are executed in the log-domain.
Specifically, log pdf (i.e., −(x−1)2/2 σ) is calculated using received data x (σ represents variance). Log γ (i.e., log (pdf.pdf.prb)) is calculated utilizing a property of logarithms (log (pdf.pdf.prb)=log pdf+log pdf+log pdf). Log λ   (            i      .      e      .        ,          log      ⁢                           ⁢                        ∑                      (                          α              ·              β              ·              γ                        )                                    ∑                      (                          α              ·              β              ·              γ                        )                                )is also calculated utilizing a property of logarithms       (                  log        ⁢                                   ⁢                              ∑                          (                              α                ·                β                ·                γ                            )                                            ∑                          (                              α                ·                β                ·                γ                            )                                          =                        log          ⁢                      ∑                          (                              α                ·                β                ·                γ                            )                                      -                  log          ⁢                      ∑                          (                              α                ·                β                ·                γ                            )                                            )    .
On the other hand, each of the probabilities a obtained by using a formula α1·γ1+α2·γ2 where α1, α2 represent the previous states in the trellis and γ1, γ2 represent the branches of the respective previous states α1, α2. Therefore, putting α1·γ1=ea and α2·γ2=eb, log (ea+eb) should be calculated for obtaining the value of log α. Similarly, each of the probabilities β is obtained by using a formula β1·γ3+β2·γ4 where β1, β2 represent the previous states in the trellis and γ3, γ4 represent the branches of the respective previous state β1, β2. Therefore, putting β1·γ3=ea and β2·γ4=eb, log (ea+eb) should be calculated for obtaining the value of log β.
When inequality a>b is satisfied, log (ea+eb) equals log ea(1+eb−a) and therefore equals “a+log (1+eb−a)”. When inequality b>a is satisfied, log (ea+eb) equals log eb(1+ea−b) and therefore equals “b+log (1+ea−b)”. Accordingly, log (ea+eb) is represented by the following formula:log (ea+eb)=max (a, b)+log (1+e−|a−b|)  (1)
It is proposed that the second term log (1+e−|a−b|) of formula (1) is obtained by table lookup (NAGATA et al., “VLSI Implementation and Evaluation of W-CDMA Turbo Decoder”, B-5-26, p. 411, 2000, Institute of Electronics, Information and Communication Engineers). In this case, formula (1) is calculated as follows.
Referring to FIG. 10, a subtracter 301 receives input data a, b, and outputs the difference (a−b) between the input data a and b to a selector 302 and a table lookup block 303. The selector 302 further receives the input data a, b, and selects the larger one max (a, b) from the input data a and b based on the sign of the difference (a−b). The selector 302 outputs the selected larger one max (a, b) to an adder 304. The table lookup block 303 retrieves a value of log (1+e−|a−b|) from a lookup table based on the value of the difference (a−b), and outputs it to the adder 304. The adder 304 generates the sum of the values of the larger one max (a, b) and log (1+e−|a−b|), and outputs the generated sum as output y.
Thus log (ea+eb) can be calculated using the lookup table by a calculator shown in FIG. 10. However, in this case, the lookup table should include values of log (1+e−|a−b|) corresponding to relatively many sampling points in order to maintain the precision of decoding. Further, putting 1dk=x, log (1+e−x) should be calculated for obtaining the value of log prb. When an approximate value of log (1+e−x) is calculated using a lookup table, the lookup table should include values of log (1+e−x) corresponding to relatively many sampling points in order to maintain the precision of decoding. Therefore, the scale of a circuit which implements the calculator that generates an approximate value of log (1+e−|a−b|) or log (1+e−|a−b|) using a lookup table may be relatively large, and computation may be relatively complex.
This problem is not limited to the case of log (1+e−|a−b|) or log (1+e−x). When the value of an arbitrary non-linear function is obtained from a lookup table, the value of the non-linear function at a sampling point is used as the value of all the points belonging to the interval between the sampling point and the following sampling point as shown in FIG. 11. Therefore the lookup table should include values corresponding to relatively many sampling points in order to provide an approximate value sufficiently close to the actual value. However, a circuit that implements a calculator that includes a large lookup table may be relatively large-scale.
Then it is proposed that the non-linear function between two consecutive sampling points is linear-interpolated for compensating the insufficiency of the number of the sampling points. However, the calculator should perform division and multiplication for obtaining an approximate value in this case, because the slopes of straight lines that interpolate the non-linear function are unrestricted. Therefore, computation is complex, and the scale of a circuit that implements the calculator is relatively large in this case. Thus, in the case that the value of a non-linear function is digitally calculated using a lookup table that includes values at sampling points, the problems that computation is relatively complex and/or the scale of a calculator circuit is relatively large arise as a rule.